\documentclass[journal]{IEEEtran}
 \usepackage{graphicx}
 \usepackage{float}
 \usepackage{hyperref}
\usepackage[utf8]{inputenc}
\usepackage[spanish]{babel}
\usepackage{algorithm}
\usepackage{algorithmic}
\graphicspath{{./images/}}
\begin{document}

\title{Algoritmos Evolutivos Paralelos aplicados al HSCP con restricciones de Deadline}
\author{Jonathan Muraña 4254556-7 \\Grupo 13 - Algoritmos Evolutivos\\ Facultad de Ingeniería, Universidad de la República\\Septiembre, 2011 }

\maketitle

\begin{abstract}

En este documento se describen el problema HCSP,  su campo de aplicación, trabajos previos revisados, las particularidades de la versión considerada. También se plantean justificaciones sobre las distintas decisiones de diseño de los algoritmos, los principales operadores utilizados y un plan de experimentos a realizar.

\end{abstract}

\begin{keywords}
algoritmos evolutivos , HCSP, deadline
\end{keywords}

\section{Introducción}
Cuando es necesario procesar grandes volúmenes de datos o realizar calculos complejos se recurre a infraestructuras de hardware de gran porte como las costosas supercomputadoras, cluster de bajo costo o tecnologías grid. En todo caso, a pesar de que las velocidades están en el orden de los gigaflops, al momento de la ejecución de las tareas, no se logra explotar totalmente la capacidad del sistema si no se plantea una buena planificación. Se debe contar entonces con un scheduler que optimice los recursos de cómputo y además no genere demasiado overhead. En este trabajo se plantean planificadores basados en algoritmos evolutivos que mejoran las heurísticas clásicas para este problema considerando además el tiempo de finalización fijado para cada tarea.

\section{Trabajos previos relevantes}
Como trabajos previos se considera thesis Nesmachnow\cite{SergioTesis} 2010 en donde se trata el problema sin restricciones de deadline, utilizando algoritmos evolutivos para su resolución. Entre otros se plantea una versión paralela del algoritmo CHC que trabaja con poblaciones reducidas.

\section{Descripción de Problema}

El proyecto elegido pertenece al área de investigación operativa.  Se trata del problema conocido como HCSP (Heterogeneous Computing Scheduling  Problem) en donde se busca encontrar una asignación de tareas en un determinado conjunto de máquinas de forma de minimizar algún objetivo. En general este objetivo es el tiempo total de ejecución o la espera del usuario, en caso de que se trate de un  servicio de cómputo. Otros objetivos a optimizar pueden ser la energía consumida, la violaciones en el tiempo estipulado para la ejecución de una tarea.\\
Como el problema es heterogeneo, las tareas no ejecutan en el mismo tiempo en cada máquina. En general habrá una máquina (la más potente de sistema) que ejecute todas las tareas más rápido que el resto, en este caso hablamos de un problema consistente, esto es precisamente que si una máquina A ejecuta una tarea más rápido que otra B, A ejecutará el resto de las tareas tambíen más rápido que B. Pero puede haber problemas en los cuales esto no se cumpla, ya sea por la diferencia en la arquitectura de las máquinas o por las características de las tareas. En este caso estamos ante un problema inconsistente (esta característica del problema es sumamente importante porque influye en la adecuación de la heurísticas utilizadas y por lo tanto en el propio AG).\\
Situando el planificador por ejemplo en un cluster paralelo, en un determinado momento se tienen N tareas, se planifican en los M procesadores y comienzan a ejecutar las que se asignaron primero. Luego se incorporan nuevas tareas a la espera. En este punto el panificador puede volver a planificar solo con las tareas que están en espera, o planificar considerando todas las tareas e interrumpir alguna tarea de las que ya están corriendo. En el caso de que se conozcan todas las tareas y tiempos de los trabajos, y que no se admitan nuevos trabajos, se trata de un escenario estático. Si el planificador conoce la información de las tareas a medida que arriban y replanifica en función de ella, se trata de un escenario dinámico. Además se podrian buscar predecir el comportamiento de los arribos y planificar tomando en cuenta esto, sería un planificador adaptativo.\\
Un planificador no preemtivo es aquel que no interrumpe las tareas luego de que se ponen en funcionamiento.\\
En este proyecto se ha optado por el modelo que se describe a continuación. Algunas decisiones se toman de forma de simplificar el problema y por considerar que si bien se alejan un poco de los planificadores reales, encierran la misma complejidad y comportamiento. Por ejemplo un scheduling dinámico se podría lograr aplicando el estático en cada arribo de tarea.\\
El escenario se considera estático, no preemtivo. La tareas no tienen precedencias o sea que son independientes y se pueden ejecutar en cualquier orden (son características de tareas de ambientes cientificos, como el cluster FING). Tampoco existen prioridades en las tareas. El objetivo es el makespan, que es el tiempo que se requiere para la finalización total y como restricción se tomará el deadline de cada trabajo, esto es, el máximo tiempo permitido para que finalice una determinada tarea.\\
¿Cuál es la duración de una tarea en cada máquina? \\
La duración de una tarea puede depender de diversos factores y es imposible de saber de antemano. Se utiliza el modelo ETC (Expected time to compute Ali 2000) que consta de una matriz donde las filas representan las tareas y las columnas las máquinas.  A partir de parámetros de consistencia y heterogeneidad se sortean los valores de las entradas. \\
Además para la estimación del deadline se utiliza un sorteo entre dos parámetros que se ajustan de modo que la instancia tenga solución. \\

\subsection{Complejidad del problema}

Como es ampliamente conocido, el HCSP es NP difícil, la resolución por medio de métodos clásicos toma tiempo exponenciales, por lo tanto el problema es abordado (para instancias realistas y se se quiere realizar una planificación inteligente) mediante heurísticas y metaheurísticas.




\section{Área de aplicación}
En la actualidad la computación de alta velocidad está orientada a el procesamiento paralelo. Más precisamente a arquitecturas de tipo cluster y grids. La planificación en este contexto se vuelve un problema importante y más aún considerando las dimensiones (ciento de unidades de procesamiento). Cómo utilizar de forma óptima los recursos de cómputo es un cuello de botella a la hora de escalar los sitemas mencionados.


\section{Solución}

Con la finalidad de encontrar una solución de calidad al HCSP con restricciones de deadline, se planteará un algoritmo genético, además como es necesario reducir los tiempos de overhead del planificador, se implementará una versión paralela. El resultado de éste trabajo será:

\begin{enumerate}
\item Algoritmo genético clásico serial para resolución de HCSP con restricciones de dealine.

\item Algorimo genético clásico paralelo para resolución de HCSP con restricciones de dealine.

\item Algoritmo CHC serial para resolución de HCSP con restricciones de deadline

\item Algoritmo CHC paralelo para resolución de HCSP con restricciones de deadline

\item Algoritmo CHC2 serial para resolución de HCSP con restricciones de deadline


\end{enumerate}



La decisión de implementar un algoritmo CHC parte de que se ha utilizado de forma satisfactoria para problemas de scheduling. Por ejemplo en Nesmachnow\cite{SergioTesis} 2010 se atacó el problema sin restricciones. El algoritmo genético clasico se implementa con el fin de realizar comparaciones.\\
El primer problema a afrontar es generar instancias de prueba.Una consideración a tener en cuenta es que si se generan deadlines se estaría en un escenario análogo al de no tener restricciones. En caso de que los deadlines sean muy reducidos es probable que las instancias no tengan solución.\\
La evaluación para saber si dada una instancia existe una planificación cualquiera que satisfaga las restricciones es un problema complejo en sí. Por lo tanto se considera que los deadlines serán en principio bastante holgados.\\
Otro problema reconocido es el de factibilizar soluciones. Luego de obtenido el individuo, si este viola las restricciones de deadline pero tiene características que otorgan un buen makespan, es probable que si le aplico determinadas operaciones al mismo para tratar de que el deadline de todas las tareas se cumpla, consiga un individuo que me represente una buena solución (una operación es por ejemplo ordenar las tareas de una misma máquina por deadline, esto no modifica el makespan y en todo caso beneficia la violación de restricciones). Este algoritmo (corrector)  de factibilización de soluciones es una de las primeras implementaciones a realizar ya que se usará tanto en heurísticas al inicializar la población como en los operadores de los algoritmos.


\section{Configuración del Algoritmo Evolutivo}

En esta sección se explica la codificación del problema, la función de fitness y los operadores utilizados.

\subsection{Codificación del cromosoma}

Tradicionalmente en los problemas de scheduling se utilizan las codificaciones orientadas a tareas o a máquinas. Se optó por la segunda opción dado que la misma permite calcular con mayor facilidad el tiempo de finalización de una tarea, necesario para saber si se cumple o no el deadline.  En la codificación oriendada a tareas se puede agregar un campo que indique la posición relativa de la tarea dentro de la máquina pero lo consideramos a priori menos conveniente a la hora de realizar evaluaciones. 
Otro motivo para usar la codificación elegida es que permite aplicar fácilmente búsquedas locales que incluyan intercambios de tareas.

\subsection{Función de fitness}
De forma de que el problema sea efectivamente un problema de maximización se tomará como función de fitness el opuesto del makespan.

%%%%%%%%%%%%%%%ACA SE PUEDE METER LA FÓRMULA%%%%%%%%%%%%%%%%%%%%%


\subsection{Inicializar la población}


La inicialización de la población se realizó implementando una asignación aleatoriamente de las tareas en cada máquina.




\section{Algoritmos utilizados}

Se realizaron tres algoritmos genéticos que comparten características similares en sus operadores. SGA, CHC y CHC2. \\

\subsection{SGA}
SGA: El algorimo genético clásico de Goldberg\cite{Gold1989} consta de un operador de cruzamiento de un punto (SPX), mutación probabilistica y selección de ruleta.\\

Llevados a la repesentación elegida, el SPX queda de la forma siguiente: Se elige un punto al azar y se intercambian las tareas (a partir de ese punto) de un padre por las correspondiente en el otro. Luego se ordenan las tareas (en cada máquina) por deadline en forma creciente  \\ 

La mutación intenta proveer de diversidad genética a la población mediante una perturbación en un individuo. En este caso se trata del intercambio de tareas, elegidas aleatoriamente, pero orientada a mejorar el makespan por caminos que no se lograrían solamente con el cruzamiento. El operador de mutación del SGA intercambiará entonces dos tareas al azar, seleccionando una de la máquina que finaliza primero, y otro de la máquina más lenta.\\

\subsection{CHC}
CHC (Cross  generation elistist selection, Heterogeneous recombination, and Cataclysmic mutation):
Es un algoritmo evolutivo elitista que utiliza cruzamiento uniforme, reinicialización de la población en lugar de mutación y restricciones de semejanza al momento de aplicar el cruzamiento.\\

El cruzamiento uniforme en el CHC intercambia con probabilidad 0,5 las tareas de un padre por la correspondiente del otro, siempre que se cumpla la restricción de cruzamiento, esto es que los progenitores difieran entre sí un determinado umbral, que se decrementa cada vez que la población no cambie. Cuando el umbral llega a cero se interpreta que se ha convergido y se reinicia la población mediate el operador de mutación del SGA.\\

Al momento de reiniciar la población se considera tomar el mejor individuo y aplicandole el operdador de mutación para generar el resto o aplicar directamente el operador a los peores individuos.\\

Tanto en  el  algoritmo clásico como en el CHC se trabaja con soluciones que no respetan las restricciones en el tiempo de finalización de las tareas. Por lo tanto estos algoritmos estan orientados a minimizar principalmente el makespan y el deadline no se considera salvo en la ordenación local de las tareas por deadline. En el CHC2 sin embargo, solo se consideran soluciones factibles (con violación cero).

\subsection{CHC2}

Este algoritmo  tiene dos estapas:\\


Etapa 1: En esta instancia el algoritmo intenta encontrar soluciones con violacion de deadline cero, sin considerar el makespan. Partiendo de soluciones aleatorias, el fitness de cada individuo es el opuesto de las suma de la violación de cada tarea, o sea

\[ 
	Fitness = \sum_{i=1}^{NT} (T_{if} – T_{id})
	\]
	
		Si $T_{if} > T_{id}$\\
$T_{if}$ = tiempo en que finaliza la tarea i\\
$T_{id}$ = deadline de la tarea i\\

La etapa finaliza cuando el algoritmo encuentra N individuos diferentes (N tamaño de población), tal que su fitness sea cero.\\


Etapa 2: En esta estapa el fitness de los individuos es el makespan\\

$Fitness = max_i (T_{if})$\\

La población inicial es la generada en la etapa anterior. Al cruzar dos individuos, se aplica el algoritmo corrector a los hijos, si no se logra factibilizar, se vuelven a cruzar. Si se sobrepasa el número de intentos los padres se mantienen en la población.\\
\\
Otras Implementaciones\\

Generador de instancias:\\ 
Para generar las instancias se partió del generador utilizado en Nesmachnow 2008 que proporciona a partir de parámetros de consistencia y heterogeneidad instancias para el HCSP clásico. En este trabajo se complementan las instancias agregandoles un valor de deadline para cada tarea.\\
De forma de que la instancia tenga solución al asignar el tiempo de finalización de cada tarea, y que además no sea demasiado holgada, los dealines se construyen aplicando una heurística clásica, por ejemplo minmin. Dada la planificación encontrada, el tiempo en que finaliza cada tarea será su deadline. Esta instancia tiene solución siempre (la planificación MinMin). Para que la instancia no sea tan rígida se aplica un operador probabilístico a cada valor de fin.\\
\[
Dt_i = \Phi_{\mu,\sigma^2}
\]
Donde\\
$\mu    = p.DmmTi$ \\
$\sigma^2=DmmTi$ \\
$Dt_i$ = Deadline de la tarea i\\
$Dmmt_i$ = Instante en que finaliza la tarea i al aplicar MinMin\\
$p$ = coeficiente de rigidez\\

Algortimo Corrector

Dada una solución, este algoritmo intentará reubicar las tareas  que están terminando su ejecucuión después del tiempo estipulado. Luego que se encuentra una tarea se la ubica en una nueva máquina siempre y cuando no afecte el deadline de las tareas posteriores. El algoritmo se ejecuta un núnero determinado de veces hasta que la solución sea factible o hasta que no varie.



\begin{algorithmic}[1]
\WHILE {No mejora AND NOT Cantidad Iteraciones}
\STATE Buscar Tarea Que Viole Deadline
\STATE Buscar Nueva Máquina y Posición
\IF{ Encontré Lugar}
\STATE Reubico la Tarea
\ENDIF
\ENDWHILE
\end{algorithmic}


\section{Framework}
La implementación de todos los algoritmos se realizará en C++, utilizando la biblioteca MALLBA.
La implementaciones paralelas se harán basadas en la implementación mpich de MPI.

\section{Plataforma Computacional}
Se ejecuto en el entrno pcunix provisto por Facultad de Ineniería, UdelaR.\\


\begin{tabular}{l l l}
GNU Linux&kernel 2.6.35.13 & x86\_64 \\
\end{tabular}

Contiene 2 procesadores con las siguientes características\\
\begin{tabular}{ l l }
\multicolumn{2}{l}{CPU Info} \\ \hline
Model			&: Intel(R) Pentium(R) D CPU 2.80GHz\\
cpu MHz         &: 2800.000\\
cache size      &: 1024 KB\\
cpu cores       &: 2\\
&\\
\multicolumn{2}{l}{MEM Info} \\ \hline
MemTotal		&:1991380 kB\\
SwapTotal		&:1048572 kB\\
\end{tabular}\\


\section{Calibración}
La calibración se realizó para los algorimos newGA y CHC con una instancia reducida del problema.\\
En el algoritmos clásico se varío el cruzamiento (0.4;0.5;0.6), la mutacion (0.01;0.05;0.1).  En el CHC se varió el cruzamiento (0.4;0.5;0.6), la divergencia (0.7;0.8;0.9).\\


\begin{table}

\begin{tabular}{c c c}
Mutación&	Cruzamiento&	Fitness\\ \hline
0.01&		0.4&			5332,64\\
0.01&		0.5&			5021,89\\
0.01&		0.6&			5087,33\\
0.05&		0.4&			3660,15\\
0.05&		0.5&			3778,34\\
0.05&		0.6&			3422,55\\
0.1&		0.4&			3040,07\\
0.1&		0.5&			3081,8\\	
0.1&		0.6&			3125,96\\
\end{tabular}
\caption{Calibración GA Clásico}
\end{table}		



\begin{table}
\begin{tabular}{c c c c}
Selección	&	Cruzamiento	&	Divergencia	&	Fitness	\\ \hline
	0,7		&		0,4		&		0,7		&	1561,67	\\
	0,7		&		0,4		&		0,8		&	1475,89	\\
	0,7		&		0,4		&		0,9		&	1511,51	\\
	0,7		&		0,5		&		0,7		&	1523,38	\\
	0,7		&		0,5		&		0,8		&	1491,05	\\
	0,7		&		0,5		&		0,9		&	1542,05	\\
	0,7		&		0,6		&		0,7		&	1563,8	\\
	0,7		&		0,6		&		0,8		&	1551,47	\\
	0,7		&		0,6		&		0,9		&	1577,76	\\
	0,8		&		0,4		&		0,7		&	1537,77	\\
	0,8		&		0,4		&		0,8		&	1607,42	\\
	0,8		&		0,4		&		0,9		&	1561,81	\\
	0,8		&		0,5		&		0,7		&	1565,52	\\
	0,8		&		0,5		&		0,8		&	1552,41	\\
	0,8		&		0,5		&		0,9		&	1511,72	\\
	0,8		&		0,6		&		0,7		&	1557,67	\\
	0,8		&		0,6		&		0,8		&	1540,89	\\
	0,8		&		0,6		&		0,9		&	1548,06	\\
	0,9		&		0,4		&		0,7		&	1572,47	\\
	0,9		&		0,4		&		0,8		&	1622,69	\\
	0,9		&		0,4		&		0,9		&	1601,14	\\
	0,9		&		0,5		&		0,7		&	1552,21	\\
	0,9		&		0,5		&		0,8		&	1558,78	\\
	0,9		&		0,5		&		0,9		&	1633,08	\\
	0,9		&		0,6		&		0,7		&	1573,73	\\
	0,9		&		0,6		&		0,8		&	1617,27	\\
	0,9		&		0,6		&		0,9		&	1567,83	\\
\end{tabular}
\caption{Calibración CHC}
\end{table}

La mejor configuración en cada caso fue:\\


\begin{tabular}{|c |c|}
\hline
Cruzamiento	&	0.4\\ \hline
Mutación	&	0.1\\ \hline
\multicolumn{2}{c}{Mejores Parámetros para AG } 
\end{tabular}
\\
\\

\begin{tabular}{|c |c|}
\hline
Cruzamiento	&	0.4\\ \hline
Divergencia	&	0.8\\ \hline
Selección	&	0.7\\ \hline
\multicolumn{2}{c}{Mejores Parámetros para CHC } 
\end{tabular}
\\
\\

El tamaño de la población se determino luego de la etapa de calibración. Una vez obtenidos los demás parámetros, considerando un compromiso entre el tiempo de ejecución y la calidad de los resultados.

\begin{tabular}{|c |c|}
\hline
newGA	&	100\\ \hline
CHC		&	200\\ \hline
CHC2	&	50\\ \hline
\multicolumn{2}{c}{Tamaños de población } 
\end{tabular}
\\
\\


\section{Experimentos realizados y presentación de resultados}

La dimensión de la instancia de prueba considerada fue 128x8 consistente, cuya planificación resuelta con la heurística MinMin tiene un MakeSpan igual a 1604.
Dado que se trata de un algoritmo planificador los tiempos de ejecuciones deben ser reducidos se consideraron ejecuciones en el entorno de los 50 segundos, ajustando el número de iteraciones, con 10 ejecuciones independientes. \\

\bigskip

Secuencial:\\

\begin{tabular}{|c|c|c|c|}
\hline
Fitness		&	NewGA	&	CHC		&	CHC2\\ \hline
Promedio	&	2505.44 &	1446.72 &	1544.9\\ \hline 
Mejor		&	2453.98 &	1410.68 &	1499\\ \hline
Desviación	&	146 	&	19.5 	&	28.6\\ \hline

\multicolumn{4}{c}{Resultados de los algoritmos seriales} 
\end{tabular}
\\
\\
Observando el cuadro anterior vemos que el Algoritmo Clásico no logró superar a la heurística MinMin, mientras que el CHC y el CHC2 si lo hicieron. También se observa que el MakeSpan del CHC es mejor CHC2, como es de esperarse ya que en las soluciones encontradas por el primero existe eventualmente violación en el tiempo de finalización de las tareas, ya que éste trabaja con individuos no necesariamente factibles. En cambio el CHC2 reduce su dominio solamente a las soluciones que tienen suma de deadlines cero, por lo tanto descarta un conjunto de soluciones que podrían tener mejor Makespan. Además se intuye que es más dificil acercarse a los óptimos restringiendo a que la población tenga solamente individuos factibles. De la desviación estándar se concluye que los CHC son mucho más determinísticos que el AG simple. 
\\
\\
A continuación se plantean gráficas (Tiempo x vs Fitness y) para ver la variación del Makespan al aumentar el esfuerzo computacional y por lo tanto el tiempo de ejecución de los algoritmos.\\


\begin{figure}[htb]
\includegraphics[scale=0.7]{Todas}
\caption{Evolución y comparación Fitness NewGA, CHC y MinMin}
\label{fig:todas}
\end{figure}

\begin{figure}[htb]
\includegraphics[scale=0.7]{newGA}
\caption{Evolución del fitness para GA}
\label{fig:newga}
\end{figure}

\begin{figure}[htb]
\includegraphics[scale=0.7]{CHC}
\caption{Evolución del fitness para CHC}
\label{fig:chc}
\end{figure}

\begin{figure}[htb]
\includegraphics[scale=0.7]{deadlineCHC}
\caption{Evolución del deadline para CHC}
\label{fig:deadlinechc}
\end{figure}

\begin{figure}[htb]
\includegraphics[scale=0.7]{CHC2}
\caption{Evolución del Fitness para CHC2}
\label{fig:chc2}
\end{figure}



\section{Paralelo}

La implementación paralela está basada en N subpoblaciones que evolucionan independientemente y cada cierta frecuencia intercambian individuos. A continuacion se muestran los resultados de la ejecuciónes paralelas para el algoritmo SGA y el CHC considerando distinta cantidad de demes.

\bigskip

\begin{tabular}{|c|c|c|c|}
\hline
Fitness		&	Tiempo	&	Demes\\ \hline
1911.16 	&	38		&	7\\ \hline 
1790.17	&	47		&	6\\ \hline 
1779.27 	&	41		&	5\\ \hline 
1685.27 	&	36		&	4\\ \hline 
1909.12 	&	36		&	3\\ \hline 
1942.45 	&	35		&	2\\ \hline 

\multicolumn{3}{c}{Resultados SGA Paralelo} 
\end{tabular}
\\

\bigskip

\begin{tabular}{|c|c|c|c|}
\hline
Fitness		&	Tiempo	&	Demes\\ \hline
1837.29 	&	52		&	7\\ \hline 
1805.5	&	48		&	6\\ \hline 
1850.99 	&	48		&	5\\ \hline 
1818.12 	&	33		&	4\\ \hline 
1882.57 	&	18		&	3\\ \hline 
1926.96 	&	18		&	2\\ \hline 

\multicolumn{3}{c}{Resultados CHC Paralelo} 
\end{tabular}
\\

\bigskip

\section{Conclusiones}

Como principal conclusión se puede decir que se alcanzó el primer objetivo de este trabajo que era encontrar una instancia que mejorara a la heurística MinMin considerando además deadlines  en el tiempo de fin de las tarea. No se puede dejar de decir sin embargo que el esfuerzo computacional registrado para ello superó el de la heurística y que la mejora fue de tan solo un 0.9 \% ciento. Si tomamos en cuenta que la heurística MinMin es muy buena y que el makespan proporcionado esté muy cerca del óptimo el porcentaje ganado puede ser más significativo.\\

En ocaciones, en la implementación de los operadores de los algoritmos se dejó de lado el tema performace lo que pudo haber impactado en los tiempos (por ejemplo insertar en orden en vez de reordenar luego de las inserciones).\\
Otra cosa que se considera positiva es la elección del CHC como versión de algoritmo a utilizar dado que el SGA no logró buenos resultados. Además, considerando que los operadores manejan básicamente las mismas, sorprende la diferencia registrada.\\
En cuanto a las implementaciones paralelas, con ninguna se lograron buenos resultados más allá de que en el caso del SGA se superó al algoritmo serial. Se atribuyé esto al que la dimensión de la instancia considerada no era lo suficientemente grande y además las ejecusiónes se limitaron a tiempos reducidos (en el entorno de los 50 segundos)


\nocite{*}
\bibliographystyle{IEEEtran}
\bibliography{HCSP_Bibliografia.bib}



\end{document}
